home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / mozilla-firefox / include / js / jsscope.h < prev    next >
C/C++ Source or Header  |  2006-05-08  |  20KB  |  395 lines
  1. /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  2.  *
  3.  * ***** BEGIN LICENSE BLOCK *****
  4.  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
  5.  *
  6.  * The contents of this file are subject to the Mozilla Public License Version
  7.  * 1.1 (the "License"); you may not use this file except in compliance with
  8.  * the License. You may obtain a copy of the License at
  9.  * http://www.mozilla.org/MPL/
  10.  *
  11.  * Software distributed under the License is distributed on an "AS IS" basis,
  12.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13.  * for the specific language governing rights and limitations under the
  14.  * License.
  15.  *
  16.  * The Original Code is Mozilla Communicator client code, released
  17.  * March 31, 1998.
  18.  *
  19.  * The Initial Developer of the Original Code is
  20.  * Netscape Communications Corporation.
  21.  * Portions created by the Initial Developer are Copyright (C) 1998
  22.  * the Initial Developer. All Rights Reserved.
  23.  *
  24.  * Contributor(s):
  25.  *
  26.  * Alternatively, the contents of this file may be used under the terms of
  27.  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28.  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29.  * in which case the provisions of the GPL or the LGPL are applicable instead
  30.  * of those above. If you wish to allow use of your version of this file only
  31.  * under the terms of either the GPL or the LGPL, and not to allow others to
  32.  * use your version of this file under the terms of the MPL, indicate your
  33.  * decision by deleting the provisions above and replace them with the notice
  34.  * and other provisions required by the GPL or the LGPL. If you do not delete
  35.  * the provisions above, a recipient may use your version of this file under
  36.  * the terms of any one of the MPL, the GPL or the LGPL.
  37.  *
  38.  * ***** END LICENSE BLOCK ***** */
  39.  
  40. #ifndef jsscope_h___
  41. #define jsscope_h___
  42. /*
  43.  * JS symbol tables.
  44.  */
  45. #include "jstypes.h"
  46. #include "jsobj.h"
  47. #include "jsprvtd.h"
  48. #include "jspubtd.h"
  49.  
  50. #ifdef JS_THREADSAFE
  51. # include "jslock.h"
  52. #endif
  53.  
  54. /*
  55.  * Given P independent, non-unique properties each of size S words mapped by
  56.  * all scopes in a runtime, construct a property tree of N nodes each of size
  57.  * S+L words (L for tree linkage).  A nominal L value is 2 for leftmost-child
  58.  * and right-sibling links.  We hope that the N < P by enough that the space
  59.  * overhead of L, and the overhead of scope entries pointing at property tree
  60.  * nodes, is worth it.
  61.  *
  62.  * The tree construction goes as follows.  If any empty scope in the runtime
  63.  * has a property X added to it, find or create a node under the tree root
  64.  * labeled X, and set scope->lastProp to point at that node.  If any non-empty
  65.  * scope whose most recently added property is labeled Y has another property
  66.  * labeled Z added, find or create a node for Z under the node that was added
  67.  * for Y, and set scope->lastProp to point at that node.
  68.  *
  69.  * A property is labeled by its members' values: id, getter, setter, slot,
  70.  * attributes, tiny or short id, and a field telling for..in order.  Note that
  71.  * labels are not unique in the tree, but they are unique among a node's kids
  72.  * (barring rare and benign multi-threaded race condition outcomes, see below)
  73.  * and along any ancestor line from the tree root to a given leaf node (except
  74.  * for the hard case of duplicate formal parameters to a function).
  75.  *
  76.  * Thus the root of the tree represents all empty scopes, and the first ply
  77.  * of the tree represents all scopes containing one property, etc.  Each node
  78.  * in the tree can stand for any number of scopes having the same ordered set
  79.  * of properties, where that node was the last added to the scope.  (We need
  80.  * not store the root of the tree as a node, and do not -- all we need are
  81.  * links to its kids.)
  82.  *
  83.  * Sidebar on for..in loop order: ECMA requires no particular order, but this
  84.  * implementation has promised and delivered property definition order, and
  85.  * compatibility is king.  We could use an order number per property, which
  86.  * would require a sort in js_Enumerate, and an entry order generation number
  87.  * per scope.  An order number beats a list, which should be doubly-linked for
  88.  * O(1) delete.  An even better scheme is to use a parent link in the property
  89.  * tree, so that the ancestor line can be iterated from scope->lastProp when
  90.  * filling in a JSIdArray from back to front.  This parent link also helps the
  91.  * GC to sweep properties iteratively.
  92.  *
  93.  * What if a property Y is deleted from a scope?  If Y is the last property in
  94.  * the scope, we simply adjust the scope's lastProp member after we remove the
  95.  * scope's hash-table entry pointing at that property node.  The parent link
  96.  * mentioned in the for..in sidebar above makes this adjustment O(1).  But if
  97.  * Y comes between X and Z in the scope, then we might have to "fork" the tree
  98.  * at X, leaving X->Y->Z in case other scopes have those properties added in
  99.  * that order; and to finish the fork, we'd add a node labeled Z with the path
  100.  * X->Z, if it doesn't exist.  This could lead to lots of extra nodes, and to
  101.  * O(n^2) growth when deleting lots of properties.
  102.  *
  103.  * Rather, for O(1) growth all around, we should share the path X->Y->Z among
  104.  * scopes having those three properties added in that order, and among scopes
  105.  * having only X->Z where Y was deleted.  All such scopes have a lastProp that
  106.  * points to the Z child of Y.  But a scope in which Y was deleted does not
  107.  * have a table entry for Y, and when iterating that scope by traversing the
  108.  * ancestor line from Z, we will have to test for a table entry for each node,
  109.  * skipping nodes that lack entries.
  110.  *
  111.  * What if we add Y again?  X->Y->Z->Y is wrong and we'll enumerate Y twice.
  112.  * Therefore we must fork in such a case, if not earlier.  Because delete is
  113.  * "bursty", we should not fork eagerly.  Delaying a fork till we are at risk
  114.  * of adding Y after it was deleted already requires a flag in the JSScope, to
  115.  * wit, SCOPE_MIDDLE_DELETE.
  116.  *
  117.  * What about thread safety?  If the property tree operations done by requests
  118.  * are find-node and insert-node, then the only hazard is duplicate insertion.
  119.  * This is harmless except for minor bloat.  When all requests have ended or
  120.  * been suspended, the GC is free to sweep the tree after marking all nodes
  121.  * reachable from scopes, performing remove-node operations as needed.  Note
  122.  * also that the stable storage of the property nodes during active requests
  123.  * permits the property cache (see jsinterp.h) to dereference JSScopeProperty
  124.  * weak references safely.
  125.  *
  126.  * Is the property tree worth it compared to property storage in each table's
  127.  * entries?  To decide, we must find the relation <> between the words used
  128.  * with a property tree and the words required without a tree.
  129.  *
  130.  * Model all scopes as one super-scope of capacity T entries (T a power of 2).
  131.  * Let alpha be the load factor of this double hash-table.  With the property
  132.  * tree, each entry in the table is a word-sized pointer to a node that can be
  133.  * shared by many scopes.  But all such pointers are overhead compared to the
  134.  * situation without the property tree, where the table stores property nodes
  135.  * directly, as entries each of size S words.  With the property tree, we need
  136.  * L=2 extra words per node for siblings and kids pointers.  Without the tree,
  137.  * (1-alpha)*S*T words are wasted on free or removed sentinel-entries required
  138.  * by double hashing.
  139.  *
  140.  * Therefore,
  141.  *
  142.  *      (property tree)                 <> (no property tree)
  143.  *      N*(S+L) + T                     <> S*T
  144.  *      N*(S+L) + T                     <> P*S + (1-alpha)*S*T
  145.  *      N*(S+L) + alpha*T + (1-alpha)*T <> P*S + (1-alpha)*S*T
  146.  *
  147.  * Note that P is alpha*T by definition, so
  148.  *
  149.  *      N*(S+L) + P + (1-alpha)*T <> P*S + (1-alpha)*S*T
  150.  *      N*(S+L)                   <> P*S - P + (1-alpha)*S*T - (1-alpha)*T
  151.  *      N*(S+L)                   <> (P + (1-alpha)*T) * (S-1)
  152.  *      N*(S+L)                   <> (P + (1-alpha)*P/alpha) * (S-1)
  153.  *      N*(S+L)                   <> P * (1/alpha) * (S-1)
  154.  *
  155.  * Let N = P*beta for a compression ratio beta, beta <= 1:
  156.  *
  157.  *      P*beta*(S+L) <> P * (1/alpha) * (S-1)
  158.  *      beta*(S+L)   <> (S-1)/alpha
  159.  *      beta         <> (S-1)/((S+L)*alpha)
  160.  *
  161.  * For S = 6 (32-bit architectures) and L = 2, the property tree wins iff
  162.  *
  163.  *      beta < 5/(8*alpha)
  164.  *
  165.  * We ensure that alpha <= .75, so the property tree wins if beta < .83_.  An
  166.  * average beta from recent Mozilla browser startups was around .6.
  167.  *
  168.  * Can we reduce L?  Observe that the property tree degenerates into a list of
  169.  * lists if at most one property Y follows X in all scopes.  In or near such a
  170.  * case, we waste a word on the right-sibling link outside of the root ply of
  171.  * the tree.  Note also that the root ply tends to be large, so O(n^2) growth
  172.  * searching it is likely, indicating the need for hashing (but with increased
  173.  * thread safety costs).
  174.  *
  175.  * If only K out of N nodes in the property tree have more than one child, we
  176.  * could eliminate the sibling link and overlay a children list or hash-table
  177.  * pointer on the leftmost-child link (which would then be either null or an
  178.  * only-child link; the overlay could be tagged in the low bit of the pointer,
  179.  * or flagged elsewhere in the property tree node, although such a flag must
  180.  * not be considered when comparing node labels during tree search).
  181.  *
  182.  * For such a system, L = 1 + (K * averageChildrenTableSize) / N instead of 2.
  183.  * If K << N, L approaches 1 and the property tree wins if beta < .95.
  184.  *
  185.  * We observe that fan-out below the root ply of the property tree appears to
  186.  * have extremely low degree (see the MeterPropertyTree code that histograms
  187.  * child-counts in jsscope.c), so instead of a hash-table we use a linked list
  188.  * of child node pointer arrays ("kid chunks").  The details are isolated in
  189.  * jsscope.c; others must treat JSScopeProperty.kids as opaque.  We leave it
  190.  * strongly typed for debug-ability of the common (null or one-kid) cases.
  191.  *
  192.  * One final twist (can you stand it?): the mean number of entries per scope
  193.  * in Mozilla is < 5, with a large standard deviation (~8).  Instead of always
  194.  * allocating scope->table, we leave it null while initializing all the other
  195.  * scope members as if it were non-null and minimal-length.  Until a property
  196.  * is added that crosses the threshold of 6 or more entries for hashing, or
  197.  * until a "middle delete" occurs, we use linear search from scope->lastProp
  198.  * to find a given id, and save on the space overhead of a hash table.
  199.  */
  200.  
  201. struct JSScope {
  202.     JSObjectMap     map;                /* base class state */
  203.     JSObject        *object;            /* object that owns this scope */
  204.     uint8           flags;              /* flags, see below */
  205.     int8            hashShift;          /* multiplicative hash shift */
  206.     uint16          dswIndex;           /* Deutsch-Schorr-Waite scaled index */
  207.     uint32          entryCount;         /* number of entries in table */
  208.     uint32          removedCount;       /* removed entry sentinels in table */
  209.     JSScopeProperty **table;            /* table of ptrs to shared tree nodes */
  210.     JSScopeProperty *lastProp;          /* pointer to last property added */
  211. #ifdef JS_THREADSAFE
  212.     JSContext       *ownercx;           /* creating context, NULL if shared */
  213.     JSThinLock      lock;               /* binary semaphore protecting scope */
  214.     union {                             /* union lockful and lock-free state: */
  215.         jsrefcount  count;              /* lock entry count for reentrancy */
  216.         JSScope     *link;              /* next link in rt->scopeSharingTodo */
  217.     } u;
  218. #ifdef DEBUG
  219.     const char      *file[4];           /* file where lock was (re-)taken */
  220.     unsigned int    line[4];            /* line where lock was (re-)taken */
  221. #endif
  222. #endif
  223. };
  224.  
  225. #define OBJ_SCOPE(obj)                  ((JSScope *)(obj)->map)
  226.  
  227. /* By definition, hashShift = JS_DHASH_BITS - log2(capacity). */
  228. #define SCOPE_CAPACITY(scope)           JS_BIT(JS_DHASH_BITS-(scope)->hashShift)
  229.  
  230. /* Scope flags and some macros to hide them from other files than jsscope.c. */
  231. #define SCOPE_MIDDLE_DELETE             0x0001
  232. #define SCOPE_SEALED                    0x0002
  233.  
  234. #define SCOPE_HAD_MIDDLE_DELETE(scope)  ((scope)->flags & SCOPE_MIDDLE_DELETE)
  235. #define SCOPE_SET_MIDDLE_DELETE(scope)  ((scope)->flags |= SCOPE_MIDDLE_DELETE)
  236. #define SCOPE_CLR_MIDDLE_DELETE(scope)  ((scope)->flags &= ~SCOPE_MIDDLE_DELETE)
  237.  
  238. #define SCOPE_IS_SEALED(scope)          ((scope)->flags & SCOPE_SEALED)
  239. #define SCOPE_SET_SEALED(scope)         ((scope)->flags |= SCOPE_SEALED)
  240. #if 0
  241. /*
  242.  * Don't define this, it can't be done safely because JS_LOCK_OBJ will avoid
  243.  * taking the lock if the object owns its scope and the scope is sealed.
  244.  */
  245. #define SCOPE_CLR_SEALED(scope)         ((scope)->flags &= ~SCOPE_SEALED)
  246. #endif
  247.  
  248. /*
  249.  * A little information hiding for scope->lastProp, in case it ever becomes
  250.  * a tagged pointer again.
  251.  */
  252. #define SCOPE_LAST_PROP(scope)          ((scope)->lastProp)
  253. #define SCOPE_REMOVE_LAST_PROP(scope)   ((scope)->lastProp =                  \
  254.                                          (scope)->lastProp->parent)
  255.  
  256. struct JSScopeProperty {
  257.     jsid            id;                 /* int-tagged jsval/untagged JSAtom* */
  258.     JSPropertyOp    getter;             /* getter and setter hooks or objects */
  259.     JSPropertyOp    setter;
  260.     uint32          slot;               /* index in obj->slots vector */
  261.     uint8           attrs;              /* attributes, see jsapi.h JSPROP_* */
  262.     uint8           flags;              /* flags, see below for defines */
  263.     int16           shortid;            /* tinyid, or local arg/var index */
  264.     JSScopeProperty *parent;            /* parent node, reverse for..in order */
  265.     JSScopeProperty *kids;              /* null, single child, or a tagged ptr
  266.                                            to many-kids data structure */
  267. };
  268.  
  269. /* JSScopeProperty pointer tag bit indicating a collision. */
  270. #define SPROP_COLLISION                 ((jsuword)1)
  271. #define SPROP_REMOVED                   ((JSScopeProperty *) SPROP_COLLISION)
  272.  
  273. /* Macros to get and set sprop pointer values and collision flags. */
  274. #define SPROP_IS_FREE(sprop)            ((sprop) == NULL)
  275. #define SPROP_IS_REMOVED(sprop)         ((sprop) == SPROP_REMOVED)
  276. #define SPROP_IS_LIVE(sprop)            ((sprop) > SPROP_REMOVED)
  277. #define SPROP_FLAG_COLLISION(spp,sprop) (*(spp) = (JSScopeProperty *)         \
  278.                                          ((jsuword)(sprop) | SPROP_COLLISION))
  279. #define SPROP_HAD_COLLISION(sprop)      ((jsuword)(sprop) & SPROP_COLLISION)
  280. #define SPROP_FETCH(spp)                SPROP_CLEAR_COLLISION(*(spp))
  281.  
  282. #define SPROP_CLEAR_COLLISION(sprop)                                          \
  283.     ((JSScopeProperty *) ((jsuword)(sprop) & ~SPROP_COLLISION))
  284.  
  285. #define SPROP_STORE_PRESERVING_COLLISION(spp, sprop)                          \
  286.     (*(spp) = (JSScopeProperty *) ((jsuword)(sprop)                           \
  287.                                    | SPROP_HAD_COLLISION(*(spp))))
  288.  
  289. /* Bits stored in sprop->flags. */
  290. #define SPROP_MARK                      0x01
  291. #define SPROP_IS_DUPLICATE              0x02
  292. #define SPROP_IS_ALIAS                  0x04
  293. #define SPROP_HAS_SHORTID               0x08
  294. #define SPROP_IS_HIDDEN                 0x10    /* a normally-hidden property,
  295.                                                    e.g., function arg or var */
  296.  
  297. /*
  298.  * If SPROP_HAS_SHORTID is set in sprop->flags, we use sprop->shortid rather
  299.  * than id when calling sprop's getter or setter.
  300.  */
  301. #define SPROP_USERID(sprop)                                                   \
  302.     (((sprop)->flags & SPROP_HAS_SHORTID) ? INT_TO_JSVAL((sprop)->shortid)    \
  303.                                           : ID_TO_VALUE((sprop)->id))
  304.  
  305. #define SPROP_INVALID_SLOT              0xffffffff
  306.  
  307. #define SPROP_HAS_VALID_SLOT(sprop, scope)                                    \
  308.     ((sprop)->slot < (scope)->map.freeslot)
  309.  
  310. #define SPROP_HAS_STUB_GETTER(sprop)    (!(sprop)->getter)
  311. #define SPROP_HAS_STUB_SETTER(sprop)    (!(sprop)->setter)
  312.  
  313. #define SPROP_CALL_GETTER(cx,sprop,getter,obj,obj2,vp)                        \
  314.     (!(getter) ||                                                             \
  315.      (getter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
  316. #define SPROP_CALL_SETTER(cx,sprop,setter,obj,obj2,vp)                        \
  317.     (!(setter) ||                                                             \
  318.      (setter)(cx, OBJ_THIS_OBJECT(cx,obj), SPROP_USERID(sprop), vp))
  319.  
  320. #define SPROP_GET(cx,sprop,obj,obj2,vp)                                       \
  321.     (((sprop)->attrs & JSPROP_GETTER)                                         \
  322.      ? js_InternalGetOrSet(cx, obj, (sprop)->id,                              \
  323.                            OBJECT_TO_JSVAL((sprop)->getter), JSACC_READ,      \
  324.                            0, 0, vp)                                          \
  325.      : SPROP_CALL_GETTER(cx, sprop, (sprop)->getter, obj, obj2, vp))
  326.  
  327. #define SPROP_SET(cx,sprop,obj,obj2,vp)                                       \
  328.     (((sprop)->attrs & JSPROP_SETTER)                                         \
  329.      ? js_InternalGetOrSet(cx, obj, (sprop)->id,                              \
  330.                            OBJECT_TO_JSVAL((sprop)->setter), JSACC_WRITE,     \
  331.                            1, vp, vp)                                         \
  332.      : ((sprop)->attrs & JSPROP_GETTER)                                       \
  333.      ? (JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,                    \
  334.                              JSMSG_GETTER_ONLY, NULL), JS_FALSE)              \
  335.      : SPROP_CALL_SETTER(cx, sprop, (sprop)->setter, obj, obj2, vp))
  336.  
  337. /* Macro for common expression to test for shared permanent attributes. */
  338. #define SPROP_IS_SHARED_PERMANENT(sprop)                                      \
  339.     ((~(sprop)->attrs & (JSPROP_SHARED | JSPROP_PERMANENT)) == 0)
  340.  
  341. extern JSScope *
  342. js_GetMutableScope(JSContext *cx, JSObject *obj);
  343.  
  344. extern JSScope *
  345. js_NewScope(JSContext *cx, jsrefcount nrefs, JSObjectOps *ops, JSClass *clasp,
  346.             JSObject *obj);
  347.  
  348. extern void
  349. js_DestroyScope(JSContext *cx, JSScope *scope);
  350.  
  351. #define ID_TO_VALUE(id) (JSID_IS_ATOM(id) ? ATOM_JSID_TO_JSVAL(id) :          \
  352.                          JSID_IS_OBJECT(id) ? OBJECT_JSID_TO_JSVAL(id) :      \
  353.                          (jsval)(id))
  354. #define HASH_ID(id)     (JSID_IS_ATOM(id) ? JSID_TO_ATOM(id)->number :        \
  355.                          JSID_IS_OBJECT(id) ? (jsatomid) JSID_CLRTAG(id) :    \
  356.                          (jsatomid) JSID_TO_INT(id))
  357.  
  358. extern JS_FRIEND_API(JSScopeProperty **)
  359. js_SearchScope(JSScope *scope, jsid id, JSBool adding);
  360.  
  361. #define SCOPE_GET_PROPERTY(scope, id)                                         \
  362.     SPROP_FETCH(js_SearchScope(scope, id, JS_FALSE))
  363.  
  364. #define SCOPE_HAS_PROPERTY(scope, sprop)                                      \
  365.     (SCOPE_GET_PROPERTY(scope, (sprop)->id) == (sprop))
  366.  
  367. extern JSScopeProperty *
  368. js_AddScopeProperty(JSContext *cx, JSScope *scope, jsid id,
  369.                     JSPropertyOp getter, JSPropertyOp setter, uint32 slot,
  370.                     uintN attrs, uintN flags, intN shortid);
  371.  
  372. extern JSScopeProperty *
  373. js_ChangeScopePropertyAttrs(JSContext *cx, JSScope *scope,
  374.                             JSScopeProperty *sprop, uintN attrs, uintN mask,
  375.                             JSPropertyOp getter, JSPropertyOp setter);
  376.  
  377. extern JSBool
  378. js_RemoveScopeProperty(JSContext *cx, JSScope *scope, jsid id);
  379.  
  380. extern void
  381. js_ClearScope(JSContext *cx, JSScope *scope);
  382.  
  383. #define MARK_SCOPE_PROPERTY(sprop)      ((sprop)->flags |= SPROP_MARK)
  384.  
  385. extern void
  386. js_SweepScopeProperties(JSRuntime *rt);
  387.  
  388. extern JSBool
  389. js_InitPropertyTree(JSRuntime *rt);
  390.  
  391. extern void
  392. js_FinishPropertyTree(JSRuntime *rt);
  393.  
  394. #endif /* jsscope_h___ */
  395.